package com.sxu.greedy.day4;

/**
 * 单调递增的数字
 */
public class Test19 {
    public int monotoneIncreasingDigits(int n) {
        // 将数字转为字符数组
        char[] s = Integer.toString(n).toCharArray();
        int i = 0, m = s.length;
        // 找到第一个递减的位置
        while(i+1<m&&s[i]<=s[i+1])
            i++;
        if(i == m-1)
            return n;
        // 回退
        while(i - 1>=0 && s[i]==s[i-1])
            i--;
        s[i]--;
        for(int j = i + 1; j < m; j++)
            s[j] = '9'; // 需要是字符9
        return Integer.parseInt(new String(s));
    }
}
